 1.递归联系之跳台阶
   
   题目：楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？
   步骤一
   定义一个函数f(n)
   函数的功能：函数的功能就是返回n级台阶共多少种走法；
   步骤二
   确定原问题与子问题的解
         假设第一次走 1 阶，还剩 n – 1 阶，共 f(n – 1) 种走法
         假设第一次走 2 阶，还剩 n – 2 阶，共 f(n – 2)种走法
   同理反过来推导也可以的！！
   所以f(n)=f(n-1)+f(n-2)(眼熟？斐波那契)
   步骤三
   初始值
   f(1)=1
   f(2)=2
   与斐波那契数列非常相似，只是初始值不同，大家实现下这个需求，优化思路也是一样！！
 
 2.汉诺塔 (Hanoi)
   
   1).题目
   编程实现把 A 的 n 个盘子移动到 C(盘子编号是 [1, n])
   移动要求：
       每次只能移动 1 个盘子
       大盘子必须放在小盘子下面(挪动过程中 也是如此)
   2).问题分析
   挪动1个盘子
   挪动2个盘子
   挪动3个盘子
   必须将n-1 个盘子移动到B柱上！！
       如果只有一个盘子，n==1 时，直接将盘子从A移动到C;
       如果不止一个盘子，n>=2 时，其实可以分为三步
	       将n-1 个盘子从A移动到B
           将编号为n的盘子从A移动到C
           将n-1 个盘子从B移动到C
   规律：第一步和第三部是相同的！！
package com.lg.hanoi;

public class HanoiDemo {
    public static void main(String[] args) {
        moveHanoi(3, "A", "B", "C");
    }
    //时间复杂度：O(n)
    //空间复杂度O(n)
    //定义一个方法：moveHanoi(),功能是将n个盘子从A移动到c
    // 将n-1个盘子从A移动到B
    // 将编号为n的盘子从A移动到C
    // 将n-1个盘子从B移动到C
    static void moveHanoi(int n, String a, String b, String c) {
        if(n==1){
            System.out.println("将1号盘子，从" + a + "移动到" + c);
            return;
        }
        // 将n-1个盘子从A移动到B
        moveHanoi(n-1, a , c, b);
        // 将编号为n的盘子从A移动到C
        System.out.println("将编号为" + n + "的盘子从" + a + "移动到" + c);
        // 将n-1个盘子从B移动到C
        moveHanoi(n-1, b , a, c);
    }
}

 2.递归总结
   
   如果递归调用深度较大，调用次数过多的时候，会占用较多的空间，有可能导致栈溢出(Stack Overflow)
   递归调用有时候存在大量重复调用，性能不好
   所以我们可以考虑将递归转为非递归(迭代)；
   递归百分百可以转为非递归！！
   什么是非递归？
   public static void main(String[] args) {
    sum(4);
   }
   //递归
  static  int sum(int n){
      int res=0;
      for (int i = 1; i <= n; i++) {
        res+=i;
     }
     return res;
  }

  //非递归，迭代
  static  int sum1(int n){
      if(n <=1) return n;
      return n+sum(n-1);
  }
  递归转为非递归的另一种方法：
  在某些时候可以考虑重复使用一组相同的变量来保存每个栈帧的内容
  如果之前的是递归调用，那现在就变成了非递归，使用一次循环即搞定了。
  空间复杂度：由O(n)变为了O(1)
  递归转非递归两种方式：
      自己使用栈
      考虑重复利用一组相同的变量